In this paper, we study variants of the parallel hash function construction of Damgård. We first show an improvement such that the number of processors is almost a half if |M|=(2s + 1)n for some s, where M is the message to be hashed. We next show that there exists a variant of our parallel hash construction such that it is secure even if the underlying compression function is not necessarily collision-free nor one-way. The cost is that some constant times more processors are required.

User authentication is necessary on the Internet and in mobile communications to protect the legal user's rights. One-time password authentication methods change the verifier every time by sending the present verifier along with the next verifier. However, such methods risk impersonation attacks because those protocols use two verifiers every session. The OSPA (Optimal Strong-Password Authentication) method is a one-time password method which prevents stolen-verifier problems, replay attacks, and denial of service attacks. In this letter, we devise an impersonation attack on the OSPA method and discuss how to break down the OSPA method.

This paper shows an extensive software performance analysis of dedicated hash functions, particularly concentrating on Pentium III, which is a current dominant processor. The targeted hash functions are MD5, RIPEMD-128 -160, SHA-1 -256 -512 and Whirlpool, which fully cover currently used and future promised hashing algorithms. We try to optimize hashing speed not only by carefully arranging pipeline scheduling but also by processing two or even three message blocks in parallel using MMX registers for 32-bit oriented hash functions. Moreover we thoroughly utilize 64-bit MMX instructions for maximizing performance of 64-bit oriented hash functions, SHA-512 and Whirlpool. To our best knowledge, this paper gives the first detailed measured performance analysis of SHA-256, SHA-512 and Whirlpool.

Recently, Lin et al. addressed two weaknesses of a new strong-password authentication scheme, the SAS protocol, and then proposed an improved one called the OSPA (Optimal Strong-Password Authentication) protocol. However, we find that both the OSPA protocol and the SAS protocol are vulnerable to the stolen-verifier attack.

The function of a message authentication code (MAC) is to verify the validity of a whole message. The disadvantage of usual MACs is that a receiver can not check its validity until the receipt of a message is finished. Hence, usual MACs are not suitable for verifying a large amount of data such as video and audio (called stream). In this letter, we propose a MAC such that the validity of a stream can be consecutively verified without waiting for the end of the reception. In addition, we show its implementations: one is based on practical hash functions, and the other is based on universal hash functions.

RC6 is a common-key block cipher that was proposed as one of the AES candidates. Although any weakness of RC6 in the use of the confidentiality is not known, Saarinen pointed out the existence of almost equivalent keys in RC6 with 176-byte keys. This means that the Davies-Meyer hash function based on RC6 with 176-byte keys is not a good collision-resistance function. However, Saarinen could not find a precise collision of it. In this paper, we propose a practical method for obtaining a collision of the Davies-Meyer hash function based on RC6-32/20/176. In other words, there exist equivalent user supplied keys in RC6-32/20/176, and it is possible to obtain them practically. This means that the essential key space of RC6-32/20/176 is smaller than the space provided by 176-byte keys. Our computer simulation shows that a collision can be found in about 100 minutes. We should notice that the result of this paper does not affect the security of the AES version of RC6 because RC6-32/20/176 discussed in this paper is different from the parameter of the AES version.

A password-based mechanism is the most widely used method of authentication in distributed environments. However, because people are used to choosing easy-to-remember passwords, so-called "weak-passwords," dictionary attacks on them can succeed. The techniques used to prevent dictionary attacks lead to a heavy computational load. Indeed, forcing people to use well-chosen passwords, so-called "strong passwords," with the assistance of tamper-resistant hardware devices can be regarded as another fine authentication solution. In this paper, we examine a recent solution, the SAS protocol, and demonstrate that it is vulnerable to replay and denial of service attacks. We also propose an Optimal Strong-Password Authentication (OSPA) protocol that is secure against stolen-verifier, replay, and denial of service attacks, and minimizes computation, storage, and transmission overheads.

Certificate Revocation is a critical issue for a practical, public-key infrastructure. A new efficient revocation protocol using a one-way hash tree structure (instead of the classical list structure, which is known as a standard for revocation), was proposed and examined to reduce communication and computation costs. In this paper, we analysis a k-ary hash tree for certificate revocation and prove that k = 2 minimizes communication cost.

In this paper we propose SAS-Coin, a very practical micro payment scheme based on a hash chain and a simple one time password authentication protocol called SAS. While it has many desirable features of a coin (anonymity etc.), it has no public key operations at any stage and has very little overheads. Moreover authentication is also available and a session key could be generated for encrypted information supply without any additional cost at all. Since there are no public key operations this is extremely useful for mobile telephone applications. This has sufficient security even for larger payments. Comparative analysis with some of the already proposed systems is also done.

In the Internet and Mobile communication environment, authentication of the users is very important. Although at present password is extensively used for authentication, bare password transmission suffers from some inherent shortcomings. Several password-based authentication methods have been proposed to eliminate such shortcomings. Those proposed methods have relative demerits as well as merits. In this letter we propose a method where those demerits are eliminated. The prominent feature is security improvement apart from low processing, storage and transmission overheads compared to previous methods. This method can be used in several applications like remote login, encrypted and authenticated communication and electronic payment etc.

This paper proposes an electronic soccer lottery protocol suitable for the Internet environment. Recently, protocols based on public-key schemes such as digital signature have been proposed for electronic voting systems or other similar systems. For a soccer lottery system in particular, it is important to reduce the computational complexity and the amount of communication data required, because we must expect that a large number of tickets will be purchased simultaneously. These problems can be solved by introducing hash functions as the core of protocol. This paper shows a practical soccer lottery system based on bit commitment and hash functions, in which the privacy of prize-winners is protected and illegal acts by the lottery promoter or lottery ticket shops can be revealed.

This paper proposes an efficient algorithm for finding preimages of the reduced MD4 compression function consisting of only the first round and the third round. We thus show that the reduced MD4 is not a one-way function.

We suggest an MAC scheme which combines a hash function and an block cipher in order. We strengthen this scheme to prevent the problem of leaking the intermediate hash value between the hash function and the block cipher by additional random bits. The requirements to the used hash function are loosely. Security of the proposed scheme is heavily dependent on the underlying block cipher. This scheme is efficient on software implementation for processing long messages and has clear security properties.

We analyze the security of iterated 2m-bit hash functions with rate 1 whose round functions use a block cipher with an m-bit input (output) and a 2m-bit key. We first show a preimage attack with O(2m) complexity on Yi and Lam's hash function of this type. This means that their claim is wrong and it is less secure than MDC-2. Next, it is shown that a very wide class of such functions is also less secure than MDC-2. More precisely, we prove that there exist a preimage attack and a 2nd preimage attack with O(2m) complexity and a collision attack with O(23m/4) complexity, respectively. Finally, we suggest a class of hash functions with a 2m-bit hashed value which seem to be as secure as MDC-2.

We propose new key exchange and authentication protocols, which are efficient in protecting a poorly-chosen weak secret from guessing attacks, based on the use of a one-time pad and a strong one-way hash function. Cryptographic protocols assume that a strong secret should be shared between communication participants for authentication, in the light of an ever-present threat of guessing attacks. Cryptographically long secret would be better for security only if ordinary users could remember it. But most users choose an easy-to-remember password as a secret and such a weak secret can be guessed easily. In our previous work, we made much of introducing a basic concept and its application. In this paper, we describe our idea in more detail and propose more protocols which correspond to variants of our basic protocol using well-defined notations. Formal verification and efficiency comparison of the proposed protocols are also presented. By our scheme the password guessing attacks are defeated efficiently, and a session key is exchanged and participants are authenticated securely.

This paper proposes to apply random mapping methods of a pseudo random function to find collisions of a hash function. We test a hash function including a block cipher (see ISO/IEC 10118-2) with computers, where users can select its initial vector. In particular, the paper shows that a hash function with multiple stages generates a lot of collision hash values, so our probabilistic consideration of a small model for the hash function well explains the computational results. We show that it's feasible to find collisions between the selected messages in advance for 64-bit-size hash functions with WSs linked via an ordinary LAN (Local Area Network). Thus, it is dangerous to use the hash function -- single block mode -- defined in [6] and [7].

Damgrd defined the notion of a collision intractable hash functions and showed that there exists a collection of collision intractable hash functions if there exists a collection of claw-free permutation pairs. For a long time, the necessary and sufficient condition for the existence of a collection of collision intractable hash functions has not been known, however, very recently Russell finally showed that there exists a collection of collision intractable hash functions iff there exists a collection of claw-free pseudo-permutation pairs. In this paper, we show an alternative necessary and sufficient condition for the existence of a collection of collision intractable hash functions, i.e., there exists a collection of collision intractable hash functions iff there exists a collection of distinction intractable pseudo-permutations.

This paper points out that there are two types of claw free families with respect to a level of claw freeness. We formulate them as weak claw free families and strong claw free families. Then, we present sufficient conditions for each type of claw free families. (A similar result is known for weak claw free families.) They are represented as some algebraic forms of one way functions. A new example of strong claw free families is also given.